/*
 * @Author: w
 * @Date: 2022年02月16日10:19:49
 * @Description: 4. 寻找两个正序数组的中位数   算法的时间复杂度应该为 O(log (m+n))
 */

// 我1 暴力  时间复杂度不符合
var findMedianSortedArrays = function (nums1, nums2) {
  const arr = [...nums1, ...nums2];
  arr.sort((a, b) => {
    return a - b;
  });
  const index = arr.length / 2;
  if (index % 1 > 0) {
    return arr[index - 0.5];
  } else {
    return (arr[index] + arr[index - 1]) / 2;
  }
};

// 我2 中间数组（合并有序数组）
// 可修改为双指针 减少内存占用 少一个数组
var findMedianSortedArrays = function (nums1, nums2) {
  const arr = [];
  const half = (nums1.length + nums2.length) / 2;
  const length = Math.ceil(half + 0.5);
  let i1 = 0,
    i2 = 0;
  while (arr.length < length) {
    if (nums2[i2] == undefined || nums1[i1] < nums2[i2]) {
      arr.unshift(nums1[i1]);
      i1++;
    } else {
      arr.unshift(nums2[i2]);
      i2++;
    }
  }
  if (half % 1) {
    return arr[0];
  } else {
    return (arr[1] + arr[0]) / 2;
  }
};

// 二分查找
/**
 *
 *
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  // nums1长度比nums2小
  if (nums1.length > nums2.length) {
    [nums1, nums2] = [nums2, nums1];
  }

  let m = nums1.length;
  let n = nums2.length;
  // 在0～m中查找
  let left = 0;
  let right = m;

  // median1：前一部分的最大值
  // median2：后一部分的最小值
  let median1 = 0;
  let median2 = 0;

  while (left <= right) {
    // 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]
    // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]
    const i = left + Math.floor((right - left) / 2);
    const j = Math.floor((m + n + 1) / 2) - i;

    const maxLeft1 = i === 0 ? -Infinity : nums1[i - 1];
    const minRight1 = i === m ? Infinity : nums1[i];

    const maxLeft2 = j === 0 ? -Infinity : nums2[j - 1];
    const minRight2 = j === n ? Infinity : nums2[j];

    if (maxLeft1 <= minRight2) {
      median1 = Math.max(maxLeft1, maxLeft2);
      median2 = Math.min(minRight1, minRight2);
      left = i + 1;
    } else {
      right = i - 1;
    }
  }
  return (m + n) % 2 == 0 ? (median1 + median2) / 2 : median1;
};

// 快
var findMedianSortedArrays = function (nums1, nums2) {
  let n = nums1.length + nums2.length;
  nums1.splice(nums1.length, nums2.length, ...nums2);
  nums1.sort((a, b) => a - b);
  let index = Math.floor(n / 2);
  if (n % 2 == 0) {
    return (nums1[index - 1] + nums1[index]) / 2;
  } else {
    return nums1[index];
  }
};

// 双指针
var findMedianSortedArrays = function (nums1, nums2) {
  let n1 = nums1.length;
  let n2 = nums2.length;

  // 两个数组总长度
  let len = n1 + n2;

  // 保存当前移动的指针的值(在nums1或nums2移动)，和上一个值
  let preValue = -1;
  let curValue = -1;

  //  两个指针分别在nums1和nums2上移动
  let point1 = 0;
  let point2 = 0;

  // 需要遍历len/2次，当len是奇数时，最后取curValue的值，是偶数时，最后取(preValue + curValue)/2的值
  for (let i = 0; i <= Math.floor(len / 2); i++) {
    preValue = curValue;
    // 需要在nums1上移动point1指针
    if (point1 < n1 && (point2 >= n2 || nums1[point1] < nums2[point2])) {
      curValue = nums1[point1];
      point1++;
    } else {
      curValue = nums2[point2];
      point2++;
    }
  }

  return len % 2 === 0 ? (preValue + curValue) / 2 : curValue;
};
